The development and application of rule engines is one branch of Artificial Intelligence (A.I.), which is a very broad research area that focuses on “making computers think like people.” Broadly speaking, a rule engine processes information by applying rules to data objects (also known as facts; or simply referred to as data). A rule is a logical construct for describing the operations, definitions, conditions, and/or constraints that apply to some predetermined data to achieve a goal. Various types of rule engines have been developed to evaluate and process rules. Conventionally, a rule engine implements a network to process rules and data objects, such as the example shown in FIG. 1. A network may include many different types of nodes, including, for example, object-type nodes, alpha nodes, left-input-adapter nodes, eval nodes, join nodes, not nodes, and terminal nodes, etc. Referring to FIG. 1, the network 100 includes two object-type nodes 111 and 121, two alpha nodes 113 and 123, a left-input-adapter node 115, a join node 130, and a terminal node 140.
Typically, data objects enter a network at the root node, from which they are propagated to any matching object-type nodes. From an object-type node, a data object is propagated to either an alpha node (if there is a literal constraint), a left-input-adapter node (if the data object is the left most object type for the rule), or a beta node (such as a join node). For example, referring to FIG. 1, a data object 101 is propagated to a matching object-type node 111. From the ObjectType Node 111, the data object 101 is propagated to an alpha node 113, and then to a left-input-adapter node 115. Connected to the left-input-adapter node 115 is a join node 130, which is an example of a beta node.
A beta node has two inputs, unlike one-input nodes, such as object-type nodes and alpha nodes. A beta node can receive tuples in its left-input and data objects, or simply referred to as objects, in its right-input. Join nodes, not nodes, and exist nodes are some examples of beta nodes. All nodes may have one or more memories to store a reference to the data objects and tuples propagated to them, if any. For example, a beta node can have a left memory and a right memory associated with its left input and right input, respectively. The left-input-adapter node creates a tuple with a single data object and propagates the tuple created to the left input of the first beta node connected to the left-input-adapter node, where the tuple is placed in the left memory of the beta node and then join attempts are made with all the objects in the right memory of the beta node. For example, the left-input-adapter node 115 creates a tuple 103 from the data object 101 and propagates the tuple to the join node 130. When the tuple 103 propagates into the join node 130, the tuple 103 is placed in the left memory of the join node.
When another data object 104 enters the right input of the join node, the data object 104 is placed in the right memory of the join node 130 and join attempts are made with all the tuples (including tuple 103) in the left memory of the join node 130. The tuples placed in the left memory of the join node 130 are partially matched. If a join attempt is successful, the data object 104 is added to the tuple 103, which is then propagated to the left input of the next node in the network 100. Such evaluation and propagation continue through other nodes down the network 100, if any, until the tuple 103 reaches the terminal node 140. When the tuple 103 reaches the terminal node 140, the tuple 103 is fully matched. At the terminal node 140, an activation is created from the fully matched tuple 103 and the corresponding rule. The activation is placed onto an agenda of the rule engine for potential firing or potential execution.
As mentioned above, join attempts are made with all the tuples (including tuple 103) in the left memory of the join node 130 when the data object 104 is placed into the right memory of the join node 130. However, if there are no tuples in the left memory, then no join can happen and the data object 104 just waits in the right memory until a tuple propagates to the left input and attempts to join with it. Likewise, the tuple 103 in the left memory would have to wait for data objects to propagate into the right input if the right memory had been empty. It would have been better if the rule engine could avoid populating the join node's memory until both sides have tuples and/or data objects. Conventional left and right unlinking attempts to solve the above problem.
According to one conventional approach, a node can either be left unlinked or right unlinked, but not both, as then the node would be completely disconnected from the network. Unlinking an input means that it may not receive any propagation and that the node's memory for that input will not be populated, thus saving memory space. When the opposite side, which is still linked, receives a propagation (such as a tuple or a data object), the unlinked side is linked back in and, as a result, receives all the tuples or data objects that would have propagated to the memory of the unlinked side. As both sides cannot be unlinked, a simple heuristic approach is proposed for choosing which side to unlink. Specifically, whichever side becomes empty first will cause the opposite side to be unlinked in a node. This conventional approach proposes to simply arbitrarily choose to unlink one side as default upon start up. However, if the wrong side is chosen, an initial hit on performance may be incurred.